Méthodes par différences temporelles n-Step (n-step TD Methods)

5. Apprentissage de type Off-policy sans échantillonnage préférentiel

On a vu que la méthode Q-learning a permis de réaliser un apprentissage de type Off-policy sans utiliser explicitement d'échantillonnage préférentiel ni de stratégie comportementale. L'idée est donc de se demander s'il existe un équivalent en multi-pas. C'est le but de l'algorithme que nous allons découvrir ici.

Algorithme n-step à arbre

L'idée de cet algorithme est décrite sur le diagramme suivant. Au centre, on y voit les trois états visités, les trois récompenses obtenues et les deux actions utilisées par l'agent. Ce sont les variables aléatoires qui représentent les événements qui se sont produits suite à la paire d'état-action initiale $(S_t,A_t)$. On y voit également les actions qui n'ont pas été sélectionnées (sur le dernier état, aucune des actions n'a encore été sélectionnée).

Jusqu'à présent, nous avons toujours mis à jour les estimations de la valeur de l'état en haut du diagramme en cumulant les récompenses obtenues (avec un facteur de remise), et en utlisant l'estimation de la valeur de l'état du bas.

Dans ce nouvel algorithme, et comme nous n'avons aucune donnée concernant les actions non sélectionnées, on arrête le flux et on utilise les estimations des valeurs d'actions afin de calculer la mise à jour de la cible. La cible inclut donc également l'ensemble des actions sur les côtés du diagramme, à chaque niveau. La mise à jour se faire sur l'ensemble de l'arbre à l'aide de l'estimations des valeurs des actions.

Plus précisément, les mises à jour sont calculées à partir de l'estimation des valeurs d'action se trouvant sur les feuilles de l'arbre. Les noeuds d'action interne, qui correspondent aux actions prises par l'agent, n'entre pas en compte. Chaque feuille apporte une contribution à la cible de manière proportionnelle à sa probabilité d'être prise par la stratégie $\pi$. Ainsi, chaque action $a$ contribue à la cible avec un poids de $\pi(a|S_{t+1})$, sauf l'action sélectionnée $A_{t+1}$. Sa probabilité $\pi(A_{t+1}|S_{t+1})$ est utilisée pour donner un poids à toutes les actions du second niveau. Ainsi, toutes les actions $a'$ non sélectionnées de second niveau contribuent avec poids de $\pi(A_{t+1}|S_{t+1})\pi(a'|S_{t+2})$. Toutes les actions $a''$ non sélectionnées de troisième niveau contribuent avec poids de $\pi(A_{t+1}|S_{t+1})\pi(A_{t+2}|S_{t+2})\pi(a''|S_{t+3})$, et ainsi de suite :

Mise en équations

Le revenu (cible) sur un pas est le suivant :

$${G_{t:t + 1}} = {R_{t + 1}} + \gamma {E_\pi }\left[ {Q_t\left( {{S_{t + 1}},{A_{t + 1}}} \right)|{S_{t + 1}}} \right]$$
$${G_{t:t + 1}} = {R_{t + 1}} + \gamma \sum\limits_a {\pi \left( {a|{S_{t + 1}}} \right){Q_t}\left( {{S_{t + 1}},a} \right)} , \quad t < T - 1$$

Pour un double pas, on aurait :

$${G_{t:t + 2}} = {R_{t + 1}} + \gamma \sum\limits_{a \ne {A_{t + 1}}} {\pi \left( {a|{S_{t + 1}}} \right){Q_{t + 1}}\left( {{S_{t + 1}},a} \right)} + \gamma \pi \left( {{A_{t + 1}}|{S_{t + 1}}} \right)\left( {{R_{t + 2}} + \gamma \sum\limits_a {\pi \left( {a|{S_{t + 2}}} \right){Q_{t + 1}}\left( {{S_{t + 2}},a} \right)} } \right), \quad t < T - 2$$
$${G_{t:t + 2}} = {R_{t + 1}} + \gamma \sum\limits_{a \ne {A_{t + 1}}} {\pi \left( {a|{S_{t + 1}}} \right){Q_{t + 1}}\left( {{S_{t + 1}},a} \right)} + \gamma \pi \left( {{A_{t + 1}}|{S_{t + 1}}} \right){G_{t + 1:t + 2}}, \quad t < T - 2$$

On peut donc tirer une équation récursive pour le calcul de la cible :

$${G_{t:t + n}} = {R_{t + 1}} + \gamma \sum\limits_{a \ne {A_{t + 1}}} {\pi \left( {a|{S_{t + 1}}} \right){Q_{t + n - 1}}\left( {{S_{t + 1}},a} \right) + } \gamma \pi \left( {{A_{t + 1}}|{S_{t + 1}}} \right){G_{t + 1:t + n}}, \quad t < T - 1, \quad si \: n \ge 2$$
$${G_{t:t + 1}} = {R_{t + 1}} + \gamma \sum\limits_a {\pi \left( {a|{S_{t + 1}}} \right){Q_t}\left( {{S_{t + 1}},a} \right)} , \quad si \: n = 1$$

À partir de cette équation de la cible, on peut trouver l'équation pour calculer la fonction des valeurs d'actions :

$${Q_{t + n}}\left( {{S_t},{A_t}} \right) = {Q_{t + n - 1}}\left( {{S_t},{A_t}} \right) + \alpha \left[ {{G_{t:t + n}} - {Q_{t + n - 1}}\left( {{S_t},{A_t}} \right)} \right], \quad 0 \le t \le T$$

avec les valeurs des autres paires d'états-actions qui restent inchangées : ${Q_{t + n}}\left( {s,a} \right) = {Q_{t + n - 1}}\left( {s,a} \right)$ pour tous les états $s$ et les actions $a$ tels que $s \ne S_t$ et $a \ne A_t$.

Algorithme